A conventional anonymous hierarchical-identity-based encryption system will be described. It is defined in the following description that “p” is a prime number, “G” and “GT” are cyclic groups of an order “p”, and “e” is a non-degenerate bilinear map from G×G to G. Here, “being bilinear” means that e(gα, hβ)=e(g, g)αβ holds for all α, βεZ/pZ (Z is a set of integrals) and gεG. In addition, “being non-degenerate” means that e(g, g) is a constituent member of GT for the case where “g” is a constituent member of G. “L” represents the maximum depth of the hierarchical layers, and a^b is an alternative notation of ab.
As a conventional anonymous-hierarchical-identity-based encryption system, there is a system recited in Literature-1. FIG. 9 shows a key generation device in Literature-1. The key generation device 100 receives therein a public key 101 (L, g[1], g[2], g[3], (h[1], . . . , h[L]), y) and a master key 103 (x, g[3]). The “L” is referred to as the number of hierarchical layers, whereas (h[1], . . . , h[L]) are referred to as strong hierarchical elements 102. The g[1], g[2], g[3], h[1], . . . , h[L] are elements of G, and generated so that y=g[1]α and x=g[2]α hold for the member α of Z/pZ.
The key generation device 100 also receives therein a random number 105 and an identity θ 104 (θ=(θ[1], . . . , θ[m]) ε(Z/pZ)m). The key generation device 100 generates a random number element ξ 106, which is an element of Z/pZ, from the random number 105 and outputs a secret key skey(θ) 108 corresponding to the identity θ 104 after generating the same by using the following formula:
                              skey          ⁡                      (            θ            )                          =                  (                                    d              ⁡                              [                                  θ                  ,                  0                                ]                                      ,                          d              ⁡                              [                                  θ                  ,                  1                                ]                                      ,                          d              ⁡                              [                                  θ                  ,                                      m                    +                    1                                                  ]                                      ,            …            ⁢                                                  ,                          d              ⁡                              [                                  θ                  ,                  L                                ]                                              )                                        =                              (                                                            x                  (                                                            g                      ⁡                                              [                        3                        ]                                                              ⁢                                                                                            ∏                          m                                                                          i                          =                          1                                                                    ⁢                                                                                          ⁢                                                                        h                          ⁡                                                      [                            i                            ]                                                                                                    θ                          ⁡                                                      [                            i                            ]                                                                                                                                )                                ξ                            ,                                                g                  ⁡                                      [                    1                    ]                                                  ξ                            ,                                                h                  ⁡                                      [                                          m                      +                      1                                        ]                                                  ξ                            ,              …              ⁢                                                          ,                                                h                  ⁡                                      [                    L                    ]                                                  ξ                                      )                    .                    
FIG. 10 shows the key derivation device 200 in Literature-1. The key derivation device 200 receives therein the identity θ 104 (θ=(θ[1], . . . , θ[m]), public key 101 (L, g[1], g[2], g[3], (h[1], . . . , h[L]), y), and secret key skey(θ) 108, which is expressed by skey(θ)=(d[θ, 0], d[θ, 1], d[θ, m+1], . . . , d[θ, L]). The key derivation device 200 also receives therein the random number 202 and a lower-rank identity θ* 201, θ*=(θ, θ[m+1])=(θ[1], . . . , θ[m], θ[m+1]). Here, it is defined that θ[m+1]εZ/pZ.
The key derivation device 200 generates a random number element λ203, which is an element of Z/pZ, from the random number 202, and outputs a lower-rank secret key, skey(θ*) 204, corresponding to the lower-rank identity θ* 201 after generating the same based on the following formula:
                              skey          ⁡                      (                          θ              *                        )                          =                ⁢                  (                                    d              ⁡                              [                                                      θ                    *                                    ,                  0                                ]                                      ,                          d              ⁡                              [                                                      θ                    *                                    ,                  1                                ]                                      ,                          d              ⁡                              [                                                      θ                    *                                    ,                                      m                    +                    1                                                  ]                                      ,            …            ⁢                                                  ,                          d              ⁡                              [                                                      θ                    *                                    ,                  L                                ]                                              )                                        =                ⁢                  (                                                    d                ⁡                                  [                                      θ                    ,                    0                                    ]                                            ⁢                                                (                                                            g                      ⁡                                              [                        3                        ]                                                              ⁢                                          (                                                                                                    ∏                            m                                                                                i                            =                            1                                                                          ⁢                                                                                                  ⁢                                                                              h                            ⁡                                                          [                              i                              ]                                                                                                            θ                            ⁡                                                          [                              i                              ]                                                                                                                          )                                        ⁢                                                                  d                        ⁡                                                  [                                                      θ                            ,                                                          m                              +                              1                                                                                ]                                                                                            θ                        ⁡                                                  [                                                      m                            +                            1                                                    ]                                                                                                      )                                λ                                      ,                                                                      ⁢                                                    d                ⁡                                  [                                      θ                    ,                    1                                    ]                                            ⁢                              g                λ                                      ,                                          d                ⁡                                  [                                      θ                    ,                                          m                      -                      2                                                        ]                                            ⁢                                                h                  ⁡                                      [                                          m                      +                      2                                        ]                                                  λ                                      ,            …            ⁢                                                  ,                                          d                ⁡                                  [                                      θ                    ,                    L                                    ]                                            ⁢                                                h                  ⁡                                      [                    L                    ]                                                  λ                                              )                .            
Here, it is important that assuming that ξ+λ is the random number element, the lower-rank secret key having a similar distribution can be derived in the key generation device 100, even if θ is replaced by θ*.
FIG. 11 shows the encryption device in Literature-1. The encryption device 300 receives therein the public key 101 (L, g[1], g[2], g[3], (h[1], . . . , h[L]), y), random number 302, message M301 (MεGT), and identity θ 104 (θ=(θ[1], . . . , θ[m]). The encryption device 300 generates τ that is an element of Z/pZ from the random number 302, and outputs a cyphertext ciph (θ, M) 303 after generating the same based on the following formula:ciph(θ,M)=(c[0],c[1],c[2])=(Me(g[2],y)τ,g[1]τ,(g[3]Πi=1mh[i]θ[i])τ)
FIG. 12 shows the decryption device in Literature-1. The decryption device 400 receives therein the public key 101 (L, g[1], g[2], g[3], (h[1], . . . , h[L]) y), secret key skey(θ) 108 (skey(θ)=(d[θ, 0], d[θ, 1], d[θ, m+1], . . . , d[θ, L]) and identity θ 104 (θ=(θ[1], . . . , θ[m]). The decryption device 400 also receives therein cyphertext ciph(θ, M) 303 (ciph(θ, M)=(c[0], c[1], c[2]). The decryption device 400 outputs the message M 301 after decrypting the same in the following way:M=c[0]{e(c[2],d[θ,1])/e(c[1],d[θ,0])}.
As a conventional anonymous hierarchical-identity-based broadcasting encryption technique, there is a technique described in Literature-2. FIG. 13 shows the key generation device in Literature-2. The key generation device 500 includes an input unit, an output unit, and a calculation unit (not shown). The key generation device 500 receives therein the public key 501 (L, N, p, g, g[1], . . . , g[N], g[N+2], . . . , g[2n], h[1], . . . , h[L], v, y) and master key 503 (γ, v′, y′). The L is referred to as the number of hierarchical layers, and (h[1], . . . , h[L]) are referred to as strong hierarchical elements 502. The g, y, h[1], . . . , h[L] are elements of G, and are generated so that (g′[i])i=1, . . . , 2N=(g^(α^i))i=1, . . . , 2N, and v=gγ are satisfied for the members α and γ of Z/pZ.
The key generation device 500 receives therein the random number 505, identity θ 504 (θ=(θ[1], . . . , θ[m]) ε(Z/pZ)m), and a user number “i” 507. The key generation device 500 generates a random number element ξ 506, which is an element of Z/pZ, from the random number 505, and outputs the secret key skey(i, θ) 508 corresponding to the identity θ 504 of i-th user after generating the same based on the following formula:
                              skey          ⁡                      (                          i              ,              θ                        )                          =                ⁢                  (                                    d              ⁡                              [                                  i                  ,                  θ                  ,                  0                                ]                                      ,                          d              ⁡                              [                                  i                  ,                  θ                  ,                  1                                ]                                      ,                          d              ⁡                              [                                  i                  ,                  θ                  ,                                      m                    +                    1                                                  ]                                      ,            …            ⁢                                                  ,                          d              ⁡                              [                                  i                  ,                  θ                  ,                  L                                ]                                              )                                        =                ⁢                  (                                                                      g                  ⁡                                      [                    i                    ]                                                  γ                            ⁢                                                (                                      y                    ⁢                                                                                            ∏                                                      i                            =                            1                                                                          m                                            ⁢                                                                                          ⁢                                                                        h                          ⁡                                                      [                            i                            ]                                                                                                    θ                          ⁡                                                      [                            i                            ]                                                                                                                                )                                ξ                                      ,                          g              ′ξ                        ,                                          h                ⁡                                  [                                      m                    +                    1                                    ]                                            ξ                        ,            …            ⁢                                                  ,                                          h                ⁡                                  (                  L                  )                                            ξ                                )                    
FIG. 14 shows the key derivation device in Literature-2. The key derivation device 600 receives therein the user number “i” 507, public key 501 (L, N, p, g, g[1], . . . , g[N], g[N+2], . . . , g[2n], h[1], . . . , h[L], v, y), secret key, skey(i, θ) 508, (skey(i, θ)=(d[i, θ, 0], d[i, θ, 1], d[i, θ, m+1], . . . , d[i, θ, L]) and identity θ 504 (θ=(θ[1], . . . , θ[m])). The key derivation device 600 also receives therein the random number 602 and θ*=(θ, θ[m+1])=(θ[1], . . . , θ[m], θ[m+1]), which is a lower-rank identity θ* 601. Here, it is defined that θ[m+1] εZ/pZ.
The key derivation device 600 generates the random number element λ 603, which is an element of Z/pZ, from the random number 602, and outputs the lower-rank secret key skey(i, θ*) 604 corresponding to the lower-rank identity θ* 601 after generating the same based on the following formula:
                              skey          ⁡                      (                          i              ,                              θ                *                                      )                          =                ⁢                  (                                    d              ⁡                              [                                  i                  ,                                      θ                    *                                    ,                  0                                ]                                      ,                          d              ⁡                              [                                  i                  ,                                      θ                    *                                    ,                  1                                ]                                      ,                          d              ⁡                              [                                  i                  ,                                      θ                    *                                    ,                                      m                    +                    1                                                  ]                                      ,            …            ⁢                                                  ,                          d              ⁡                              [                                  i                  ,                                      θ                    *                                    ,                  L                                ]                                              )                                        =                ⁢                  (                                                    d                ⁡                                  [                                      i                    ,                    θ                    ,                    0                                    ]                                            ⁢                                                (                                                            g                      ⁡                                              [                        3                        ]                                                              ⁢                                          (                                                                                                    ∏                                                          i                              =                              1                                                                                m                                                ⁢                                                                                                  ⁢                                                                                                                                           h                                                        ⁡                                                          [                              i                              ]                                                                                                            θ                            ⁡                                                          [                              i                              ]                                                                                                                          )                                        ⁢                                                                  d                        ⁡                                                  [                                                      i                            ,                            θ                            ,                                                          m                              +                              1                                                                                ]                                                                                            θ                        ⁡                                                  [                                                      m                            +                            1                                                    ]                                                                                                      )                                λ                                      ,                                                                      ⁢                                                    d                ⁡                                  [                                      i                    ,                    θ                    ,                    1                                    ]                                            ⁢                              g                λ                                      ,                                          d                ⁡                                  [                                      i                    ,                    θ                    ,                                          m                      +                      2                                                        ]                                            ⁢                                                h                  ⁡                                      [                                          m                      +                      2                                        ]                                                  λ                                      ,            …            ⁢                                                  ,                                          d                ⁡                                  [                                      i                    ,                    θ                    ,                    L                                    ]                                            ⁢                                                h                  ⁡                                      [                    L                    ]                                                  λ                                              )                .            It is important here that assuming that ξ+λ is the random element, the key generation device 500 can generate the lower-rank secret keys having a similar distribution even if the θ is replaced by the θ*.
FIG. 15 shows the encryption device in Literature-2. The encryption device 700 receives therein the public key 501 (L, N, p, g, g[1], . . . , g[N], g[N+2], . . . , g[2n], h[1], . . . h[L], v, y), random number 702, identity, θ, 504 (θ=(θ[1], . . . , θ[m])), and user number set S701 (S□{1, . . . , N}). The encryption device 700 generates elements, τ of Z/pZ from the random number 702, and outputs a shared key K 710 (K□GT) and cyphertext ciph(S, θ) 703 after generating the same in the following way:K=e(g[1],g[N])T;ciph(S,θ)=(c[0],c[1],c[2])=(vΠj□sg[N+1−j])T,gT,(yΠi=1mh[i]θ[i])T)
FIG. 16 shows the decryption device in Literature-2. The decryption device 800 receives therein the user number “i” 507, identity θ 504 (θ=(θ[1], . . . , θ[m])), public key 501 (L, N, p, g, g[1], . . . , g[N], g[N+2], . . . , g[2n], h[1], . . . , h[L], v, y), and secret key skey(i, θ) 508 (skey(i, θ)=(d[i, θ, 0], d[i, θ, 1], d[i, θ, m+1], . . . , d[i, θ, L]). It also receives therein the user number set S 701 for iεS and cyphertext ciph(S, θ) 703 (ciph(S, θ)=(c[0], c[1], c[2]). The decryption device 800 outputs the shared key K 710 after generating the same in the following way:K=(e(c[0],g[i])e(c[2],d[i,θ,1])/e(c[1],d[i,θ,0]ΠjεS,j=ig[N1−j+i]).
In the mean time, Literature-3 describes an elliptic curve having a bilinear map. The elliptic curve having the bilinear map described in Literature-3 has properties described hereinafter. There is a non-degenerate bilinear map “e” that is capable of configuring three cyclic groups G, G′ and GT of an order “p” and is efficient for calculation from G×G′ to GT. Here, “being bilinear” means that e(gα, hβ)=e (g, g′)αβ holds for all the α, βεZ/pZ, gεG, and g′εG′. In addition, “being degenerate” means that e(g, g′) is the constituent elements of GT if the g is the constituent element of G, and g′ is the constituent element of G′. In addition, there is a tracing map φ, which is an isomorphic map capable of efficient calculation from G′ to G, and yet the reverse calculation of φ is difficult to achieve.
[Literature-1]
Xavier Boyen, Brent Waters: Anonymous Hierarchical Identity-Based Encryption (Without Random Oracles). Advances in Cryptology, CRYPTO 2006, 26th Annual International Cryptology Conference, Santa Barbara and Calif., USA, Aug. 20-24, 2006, Proceedings, Lecture Notes in Computer Science 4117, pp. 290-307, Springer, 2006, isbn 3-540-37432-9.
[Literature-2]
Nuttapong-Attrapadung, Jun Furukawa, Hideki Imai: Forward-Secure-and-Searchable-Broadcast-Encryption-with-Short-Ciphertexts and Private Keys. Advances in Cryptology-ASIACRYPT 2006, 12th International Conference on the Theory and Application of Cryptology and Information Security, Shanghai, China, Dec. 3-7, 2006, Proceedings, Lecture Notes in Computer Science 4284, pp. 161-177, Springer, 2006, isbn 3-540-49475-8.
[Literature-3]
Atsuko Miyaji, Masaki Nakabayashi, Shunzo Takano: Characterization-of-Elliptic-Curve-Traces-under FR-Reduction. Information Security and Cryptology-ICISC 2000, Third International Conference, Seoul, Korea, Dec. 8-9, 2000, Proceedings, pp. 90-108. Lecture Notes in Computer Science 2015, Springer, 2001 year, isbn 3-540-41782-6.
In Literature-1, the cyphertext has the form of (c[0], c[1], c[2])Me(g[2], g[1]T, (g[3]Πi=1mh[i]θ[i])T). Thus, for assuring that this is the cyphertext for the identity θ, it is sufficient to ascertain that e(g[1], c[2])=e(c[1], g[3]Πi=1mh[i]θ[i])T) holds. In Literature-2, the cyphertext has the form of (c[0], c[1], c[2])=(vΠj□sg[N+1−j])T, gT, (yΠi=1mh[i]θ[i])T). Thus, for assuring that this is the cyphertext for the identity 0, it is sufficient to ascertain that e(g[1], c[2])=e(c[1], g[3]Πi=1mh[i]θ[i])T) holds, as well. The reason for the capability of assuring to which identity the cyphertext is generated in this way is that the public key includes g[3] and strong hierarchical elements h[1], . . . , h[L] in any system, and that images of bilinear map can be calculated for these values and components c[1] and c[2].
On the other hand, it is known that if there exists an anonymous identity-based encryption system, there exists an encryption system that is capable of keyword searching. The keyword-searchable encryption system is a system wherein a recipient of a cyphertext entrusts a third party with the key by which it is possible to investigate whether or not the cyphertext is generated by encrypting a specific keyword, and the third party can investigate whether or not the cyphertext is one that is generated by encrypting the keyword thus entrusted. In this case, the system is requested that the entrusted third party be incapable of knowing the content of keyword. This system may be used for a technique wherein if a mail server is entrusted with a key for the keyword search, and finds encrypted data generated by encrypting a keyword “emergency”, the mail server informs this fact to the user by a specific tool. However, the system wherein the fact that the key for the keyword allows finding of the searched word, “emergency”, is not known is a system having a higher anonymity.
If the above keyword-searchable encryption system is constructed, the fact that the searched word is not specifically known corresponds to hiding the fact that the cyphertext is created to any identity in the original identity-based encryption system. Therefore, if it is possible to hide the identity to which the cyphertext is generated, then it is possible to obtain an encryption system, a hierarchical encryption system, and a broadcasting encryption system that are capable of keyword searching. However, the conventional techniques cannot be used for this purpose.